import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.*;

public class SortingVisualizer2 extends JFrame {
    private JPanel panel;
    private JComboBox<String> algorithmBox, animationBox, dataSizeBox;
    private JButton startButton, stopButton;
    private int[] data;
    private SortAlgorithm algorithm;
    private static final int DELAY = 10; // Control animation speed
    private boolean isStopped = false;
    private boolean is2DAnimation = false; // Flag to check if 2D animation is selected

    public SortingVisualizer() {
        setTitle("排序效果图");
        setSize(800, 600);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setLayout(new BorderLayout());

        // Control Panel
        JPanel controlPanel = new JPanel();
        controlPanel.setLayout(new FlowLayout());

        algorithmBox = new JComboBox<>(new String[]{"冒泡排序", "插入排序", "选择排序", "快速排序", "归并排序", "堆排序","外部排序"});
        animationBox = new JComboBox<>(new String[]{"一维动画", "二维动画"});
        dataSizeBox = new JComboBox<>(new String[]{"50", "100", "500", "1000", "5000", "10000", "50000", "100000"});
        startButton = new JButton("开始排序");
        stopButton = new JButton("停止");

        JLabel dataSizeLabel = new JLabel("数据量级:");

        controlPanel.add(new JLabel("选择排序:"));
        controlPanel.add(algorithmBox);
        controlPanel.add(new JLabel("选择维度:"));
        controlPanel.add(animationBox);
        controlPanel.add(dataSizeLabel);
        controlPanel.add(dataSizeBox);
        controlPanel.add(startButton);
        controlPanel.add(stopButton);

        add(controlPanel, BorderLayout.NORTH);

        panel = new JPanel() {
            @Override
            protected void paintComponent(Graphics g) {
                super.paintComponent(g);
                if (data != null) {
                    int numElements = data.length;
                    int width = panel.getWidth();
                    int height = panel.getHeight();

                    g.setFont(new Font("Arial", Font.PLAIN, 12));
                    int barWidth = Math.max(1, width / numElements);
                    int maxBarHeight = height;

                    // Find the maximum value in data to scale the bars or circles
                    int maxValue = 0;
                    for (int i = 0; i < numElements; i++) {
                        if (data[i] > maxValue) {
                            maxValue = data[i];
                        }
                    }

                    // Scale factor to fit the values into the available height
                    double scaleFactor = (double) height / maxValue;

                    if (is2DAnimation) {
                        int radius = Math.max(5, (width / numElements) / 2);
                        for (int i = 0; i < numElements; i++) {
                            int x = i * (width / numElements) + (width / numElements - radius) / 2;
                            int y = height - (int) (data[i] * scaleFactor); // Scale height based on maxValue
                            g.setColor(new Color(data[i] % 255, 0, 255 - (data[i] % 255)));
                            g.fillOval(x, y - radius, radius * 2, radius * 2);

                            g.setColor(Color.BLACK);
                            g.drawString(String.valueOf(data[i]), x + radius, y - radius - 5);
                        }
                    } else {
                        for (int i = 0; i < numElements; i++) {
                            int barHeight = (int) (data[i] * scaleFactor); // Scale height based on maxValue
                            g.setColor(new Color(data[i] % 255, 0, 255 - (data[i] % 255)));
                            g.fillRect(i * barWidth, height - barHeight, barWidth, barHeight);

                            g.setColor(Color.BLACK);
                            g.drawString(String.valueOf(data[i]), i * barWidth + barWidth / 4, height - barHeight - 5);
                        }
                    }
                }
            }
        };
        add(panel, BorderLayout.CENTER);

        // Button Actions
        startButton.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent e) {
                try {
                    int dataSize = Integer.parseInt((String) dataSizeBox.getSelectedItem());
                    generateData(dataSize);
                    selectAlgorithm();
                    isStopped = false;
                    new Thread(() -> {
                        try {
                            algorithm.sort(data);
                        } catch (InterruptedException ex) {
                            ex.printStackTrace();
                        }
                    }).start();
                } catch (NumberFormatException ex) {
                    JOptionPane.showMessageDialog(SortingVisualizerNew.this, "Please enter a valid integer for data size.");
                }
            }
        });

        // Stop Button Action
        stopButton.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent e) {
                isStopped = true;
            }
        });
        animationBox.addActionListener(new ActionListener() {
            @Override
            public void actionPerformed(ActionEvent e) {
                is2DAnimation = animationBox.getSelectedIndex() == 1;
                panel.repaint();
            }
        });
    }

    private void generateData(int size) {
        data = new int[50];
        Random rand = new Random();
        for (int i = 0; i < 50; i++) {
            data[i] = rand.nextInt(size * 10 - size + 1) + size;
        }
    }

    private void selectAlgorithm() {
        String choice = (String) algorithmBox.getSelectedItem();
        switch (choice) {
            case "冒泡排序":
                algorithm = new BubbleSort();
                break;
            case "插入排序":
                algorithm = new InsertionSort();
                break;
            case "选择排序":
                algorithm = new SelectionSort();
                break;
            case "快速排序":
                algorithm = new QuickSort();
                break;
            case "归并排序":
                algorithm = new MergeSort();
                break;
            case "堆排序":
                algorithm = new HeapSort();
                break;
            case "外部排序":
                algorithm = new ExternalSort();
                break;
        }
    }

    public static void main(String[] args) {
        SwingUtilities.invokeLater(() -> {
            SortingVisualizerNew frame = new SortingVisualizerNew();
            frame.setVisible(true);
        });
    }


    interface SortAlgorithm {
        void sort(int[] data) throws InterruptedException;
    }

    class BubbleSort implements SortAlgorithm {
        @Override
        public void sort(int[] data) throws InterruptedException {
            int n = data.length;
            for (int i = 0; i < n - 1; i++) {
                for (int j = 0; j < n - i - 1; j++) {
                    if (data[j] > data[j + 1]) {
                        int temp = data[j];
                        data[j] = data[j + 1];
                        data[j + 1] = temp;
                        panel.repaint();
                        Thread.sleep(DELAY); // 延迟实现动画效果
                        if (isStopped) return; // Stop the sorting if the stop button is pressed
                    }
                }
            }
        }
    }

    class InsertionSort implements SortAlgorithm {
        @Override
        public void sort(int[] data) throws InterruptedException {
            int n = data.length;
            for (int i = 1; i < n; i++) {
                int key = data[i];
                int j = i - 1;
                while (j >= 0 && data[j] > key) {
                    data[j + 1] = data[j];
                    j = j - 1;
                    panel.repaint();
                    Thread.sleep(DELAY);
                    if (isStopped) return;
                }
                data[j + 1] = key;
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
            }
        }
    }

    class SelectionSort implements SortAlgorithm {
        @Override
        public void sort(int[] data) throws InterruptedException {
            int n = data.length;
            for (int i = 0; i < n - 1; i++) {
                int minIdx = i;
                for (int j = i + 1; j < n; j++) {
                    if (data[j] < data[minIdx]) {
                        minIdx = j;
                    }
                }
                int temp = data[minIdx];
                data[minIdx] = data[i];
                data[i] = temp;
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
            }
        }
    }


    class QuickSort implements SortAlgorithm {
        @Override
        public void sort(int[] data) throws InterruptedException {
            quickSort(data, 0, data.length - 1);
        }

        private void quickSort(int[] data, int low, int high) throws InterruptedException {
            if (low < high) {
                int pi = partition(data, low, high);
                quickSort(data, low, pi - 1);
                quickSort(data, pi + 1, high);
            }
        }

        private int partition(int[] data, int low, int high) throws InterruptedException {
            int pivot = data[high];
            int i = (low - 1);
            for (int j = low; j < high; j++) {
                if (data[j] < pivot) {
                    i++;
                    int temp = data[i];
                    data[i] = data[j];
                    data[j] = temp;
                    panel.repaint();
                    Thread.sleep(DELAY);
                    if (isStopped) return high;
                }
            }
            int temp = data[i + 1];
            data[i + 1] = data[high];
            data[high] = temp;
            panel.repaint();
            Thread.sleep(DELAY);
            if (isStopped) return high;
            return i + 1;
        }
    }

    class MergeSort implements SortAlgorithm {
        @Override
        public void sort(int[] data) throws InterruptedException {
            mergeSort(data, 0, data.length - 1);
        }

        private void mergeSort(int[] data, int left, int right) throws InterruptedException {
            if (left < right) {
                int mid = (left + right) / 2;
                mergeSort(data, left, mid);
                mergeSort(data, mid + 1, right);
                merge(data, left, mid, right);
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
            }
        }

        private void merge(int[] data, int left, int mid, int right) throws InterruptedException {
            int n1 = mid - left + 1;
            int n2 = right - mid;
            int[] L = new int[n1];
            int[] R = new int[n2];

            System.arraycopy(data, left, L, 0, n1);
            System.arraycopy(data, mid + 1, R, 0, n2);

            int i = 0, j = 0, k = left;
            while (i < n1 && j < n2) {
                if (L[i] <= R[j]) {
                    data[k] = L[i];
                    i++;
                } else {
                    data[k] = R[j];
                    j++;
                }
                k++;
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
            }
            while (i < n1) {
                data[k] = L[i];
                i++;
                k++;
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
            }
            while (j < n2) {
                data[k] = R[j];
                j++;
                k++;
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
            }
        }
    }

    class HeapSort implements SortAlgorithm {
        @Override
        public void sort(int[] data) throws InterruptedException {
            int n = data.length;
            for (int i = n / 2 - 1; i >= 0; i--) {
                heapify(data, n, i);
            }
            for (int i = n - 1; i >= 0; i--) {
                int temp = data[0];
                data[0] = data[i];
                data[i] = temp;
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
                heapify(data, i, 0);
            }
        }

        private void heapify(int[] data, int n, int i) throws InterruptedException {
            int largest = i;
            int left = 2 * i + 1;
            int right = 2 * i + 2;

            if (left < n && data[left] > data[largest]) {
                largest = left;
            }

            if (right < n && data[right] > data[largest]) {
                largest = right;
            }

            if (largest != i) {
                int swap = data[i];
                data[i] = data[largest];
                data[largest] = swap;
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return;
                heapify(data, n, largest);
            }
        }
    }

    class ExternalSort implements SortAlgorithm {
        @Override
        public void sort(int[] data) throws InterruptedException {
            externalSort(data);
        }

        private void externalSort(int[] data) throws InterruptedException {
            int chunkSize = Math.min(data.length / 10, 1000); // 模拟较小的数据块
            java.util.List<int[]> sortedChunks = new ArrayList<>();

            // Step 1: 分块并排序
            for (int i = 0; i < data.length; i += chunkSize) {
                int end = Math.min(i + chunkSize, data.length);
                int[] chunk = Arrays.copyOfRange(data, i, end);
                Arrays.sort(chunk); // 对每个块进行排序
                sortedChunks.add(chunk);

                // 每次处理完一个块后强制更新界面
                System.arraycopy(chunk, 0, data, i, chunk.length);
                panel.repaint();
                Thread.sleep(DELAY); // 延迟以展示排序进程
                if (isStopped) return;  // 如果停止了排序，退出
            }

            // Step 2: 逐步合并所有已排序的小块
            int[] mergedData = mergeChunks(sortedChunks);

            // 更新到 data 数组，最终结果展示
            System.arraycopy(mergedData, 0, data, 0, data.length);
            panel.repaint();
        }

        private int[] mergeChunks(java.util.List<int[]> chunks) throws InterruptedException {
            PriorityQueue<Element> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.value));

            // 初始化优先队列，将每个块的第一个元素放入队列
            for (int i = 0; i < chunks.size(); i++) {
                if (chunks.get(i).length > 0) {
                    pq.add(new Element(chunks.get(i)[0], i, 0));
                }
            }

            int[] mergedData = new int[chunks.stream().mapToInt(a -> a.length).sum()];
            int idx = 0;

            while (!pq.isEmpty()) {
                Element element = pq.poll();
                mergedData[idx++] = element.value;

                // 如果块中还有元素，继续加入优先队列
                int[] chunk = chunks.get(element.chunkIndex);
                if (element.elementIndex + 1 < chunk.length) {
                    pq.add(new Element(chunk[element.elementIndex + 1], element.chunkIndex, element.elementIndex + 1));
                }

                // 每次合并元素后强制更新动画
                System.arraycopy(mergedData, 0, data, 0, idx);
                panel.repaint();
                Thread.sleep(DELAY);
                if (isStopped) return new int[0]; // 提前退出
            }
            return mergedData;
        }

        // 定义一个元素类来帮助合并小块
        private  class Element {
            int value;
            int chunkIndex;
            int elementIndex;

            Element(int value, int chunkIndex, int elementIndex) {
                this.value = value;
                this.chunkIndex = chunkIndex;
                this.elementIndex = elementIndex;
            }
        }
    }




}
